package com.example.design.leetcode.dfs;

//剑指 Offer 28. 对称的二叉树
//    请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
//
//    例如，二叉树[1,2,2,3,4,4,3] 是对称的。
//
//      1
//     / \
//     2  2
//    / \ / \
//    3 4 4 3
//    但是下面这个[1,2,2,null,3,null,3] 则不是镜像对称的:
//
//      1
//     / \
//     2  2
//     \  \
//     3  3
//
//    示例 1：
//    输入：root = [1,2,2,3,4,4,3]
//    输出：true
//
//    示例 2：
//    输入：root = [1,2,2,null,3,null,3]
//    输出：false
//
//    限制：
//    0 <= 节点个数 <= 1000
//
//    注意：本题与主站 101 题相同：https://leetcode-cn.com/problems/symmetric-tree/


//表达式:
//  镜像就是：
//  树1的右子树与树2的左子树对称
//  树1的左子树与树2的右子树对称

//出口：
//    不对称：一个为null一个不为null，
//    对称：两个节点都为null
public class Practice35 {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode root1, TreeNode root2) {
        // 都为null,表示对称
        if (root1 == null && root2 == null) {
            return true;
        }
        // 只有一个为null, 表示不对称
        if (root1 == null || root2 == null) {
            return false;
        }

        return (root1.val == root2.val) && isMirror(root1.right, root2.left)
                && isMirror(root1.left, root2.right);
    }
}
